package algorithm;


public class T00020 {
    public static void main(String[] args) {
        System.out.println(new Solution().isValid("({{(([{}]))}{[()]}})"));
    }

static class Solution {
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(index > 0 && getMatchChar(stack[index - 1]) == c)
                index --;
            else {
                if(getMatchChar(c) == 0)
                    return false;
                stack[index++] = c;
            }
        }
        return index == 0;
    }

    private char getMatchChar(char c) {
        switch (c) {
            case '(': return ')';
            case '{': return '}';
            case '[': return ']';
            default: return (char) 0;
        }
    }
}
}